/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 17655
 * Date: 2025-03-02
 * Time: 12:55
 */
public class test2 {
    /**
     * LeetCode  三步问题
     */


    public int waysToStep(int n) {
        if(n==1||n==2){
            return n;
        }
        if(n==3){
            return 4;
        }
        int MOD = (int) 1e9+7;
        int [] dp = new int [n+1];
        dp[1]=1;
        dp[2]=2;
        dp[3]=4;
        for(int i=4;i<=n;i++){
            dp[i]=((dp[i-1]+dp[i-2])%MOD + dp[i-3])%MOD;
        }
        return dp[n];
    }
}
